Search results for "BINARY ALPHABETS"

showing 1 items of 1 documents

Quantum, stochastic, and pseudo stochastic languages with few states

2014

Stochastic languages are the languages recognized by probabilistic finite automata (PFAs) with cutpoint over the field of real numbers. More general computational models over the same field such as generalized finite automata (GFAs) and quantum finite automata (QFAs) define the same class. In 1963, Rabin proved the set of stochastic languages to be uncountable presenting a single 2-state PFA over the binary alphabet recognizing uncountably many languages depending on the cutpoint. In this paper, we show the same result for unary stochastic languages. Namely, we exhibit a 2-state unary GFA, a 2-state unary QFA, and a family of 3-state unary PFAs recognizing uncountably many languages; all th…

FOS: Computer and information sciencesFINITE AUTOMATAClass (set theory)Unary operationFormal Languages and Automata Theory (cs.FL)QUANTUM FINITE AUTOMATACOMPUTATIONAL MODELBINARY ALPHABETSFOS: Physical sciencesComputer Science - Formal Languages and Automata TheoryComputer Science::Computational ComplexityPROBABILISTIC FINITE AUTOMATAREAL NUMBERUNARY LANGUAGESQuantum finite automataCUT-POINTMathematicsReal numberDiscrete mathematicsQuantum PhysicsFinite-state machineGENERALIZED FINITE AUTOMATAComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)STOCHASTIC SYSTEMSAutomatonSTOCHASTIC LANGUAGESMathematics::LogicProbabilistic automatonComputer Science::Programming LanguagesQUANTUM THEORYUncountable setQuantum Physics (quant-ph)Computer Science::Formal Languages and Automata TheoryGENERALIZED FINITE AUTOMATON
researchProduct